package code.BinaryTree.在每个树行中找最大值;

import struct.Tree;
import struct.TreeNode;

import java.util.ArrayList;
import java.util.List;

class Solution {
	List<Integer> list = new ArrayList<>();//1.初始化结果数组

	public static void main(String[] args) {
		TreeNode tree = Tree.constructTree("[1,3,2,5,3,9]");
		Solution solution = new Solution();
		List<Integer> integers = solution.largestValues(tree);
		System.out.println(integers);
	}

	public List<Integer> largestValues(TreeNode root) {
		largestValuesHelper(root, 0);//3.用当前层级来更新结果
		return list;//2.返回结果数组。
	}

	private void largestValuesHelper(TreeNode root, int level) {
		if (root == null) {//4.递归终止条件。
			return;
		}
		if (list.size() == level) {//7.当前层还没有记录数据，添加数据。
			list.add(root.val);
		} else {
			list.set(level, Math.max(list.get(level), root.val));//8.更新当前层的数据。
		}
		largestValuesHelper(root.left, level + 1);//5.求解左子树，更新层级
		largestValuesHelper(root.right, level + 1);//6.求解右子树，更新层级
	}
}